﻿//根据二叉树创建字符串
// 给你二叉树的根节点 root ，请你采用前序遍历的方式，
//将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
//空节点使用一对空括号对 "()" 表示，
// 转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
//string tree2str(TreeNode* root) 
//{
//	if (root == nullptr)
//		return "";
//	string s = to_string(root->val);
//	if (root->right)
//	{
//		s += "(";
//		s += tree2str(root->left);
//		s += ")";
//		s += "(";
//		s += tree2str(root->right);
//		s += ")";
//	}
//	else if (root->left)
//	{
//		s += "(";
//		s += tree2str(root->left);
//		s += ")";
//	}
//	return s;
//}
//优化版本:(巧用逻辑或，合并相同代码)
//string tree2str(TreeNode* root) {
//    if (root == nullptr)
//        return "";
//    string s = to_string(root->val);
//    if (root->left || root->right)
//    {
//        s += "(";
//        s += tree2str(root->left);
//        s += ")";
//    }
//    if (root->right)
//    {
//        s += "(";
//        s += tree2str(root->right);
//        s += ")";
//    }
//    return s;
//}

//二叉树最近公共祖先(递归版)
//TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
//{
//    if (root == nullptr)
//        return nullptr;
//    if (root == p || root == q)
//        return root;
//
//    bool pInLeft, pInRight, qInLeft, qInRight;
//    pInLeft = Find(root->left, p);
//    pInRight = !pInLeft;
//    qInLeft = Find(root->left, q);
//    qInRight = !qInLeft;
//
//    if (pInLeft && qInLeft)
//        return lowestCommonAncestor(root->left, p, q);
//    else if (pInRight && qInRight)
//        return lowestCommonAncestor(root->right, p, q);
//    else
//        return root;
//}
//bool Find(TreeNode* root, TreeNode* tar)
//{
//    if (root == nullptr)
//        return false;
//    return root == tar ||
//        Find(root->left, tar) ||
//        Find(root->right, tar);
//}

//二叉树最近公共祖先优化版(使用栈)
//bool FindPath(TreeNode* root, TreeNode* tar, stack<TreeNode*>& st)
//{
//    if (root == nullptr)
//        return false;
//
//    st.push(root);
//    if (root == tar)
//        return true;
//
//    if (FindPath(root->left, tar, st))
//        return true;
//    if (FindPath(root->right, tar, st))
//        return true;
//
//    st.pop();
//    return false;
//}
//
//class Solution {
//public:
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
//    {
//        stack<TreeNode*> pst, qst;
//        FindPath(root, p, pst);
//        FindPath(root, q, qst);
//        while (qst.size() > pst.size())
//        {
//            qst.pop();
//        }
//
//        while (qst.size() < pst.size())
//        {
//            pst.pop();
//        }
//
//        while (qst.top() != pst.top())
//        {
//            qst.pop();
//            pst.pop();
//        }
//        return qst.top();
//    }
//};

//使用递归，如果两节点位于根节点两侧，则根节点为祖先
//若在同一侧，则判断两节点是否在这一侧的根节点的两侧，使用Find_Node来寻找在哪一侧
//bool Find_node(TreeNode* root, TreeNode* x)
//{
//    if (root == x)
//        return true;
//    if (root == nullptr)
//        return false;
//    return Find_node(root->left, x) || Find_node(root->right, x);
//}
//class Solution {
//public:
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (p == root || q == root)
//            return root;
//        if ((Find_node(root->left, p) && Find_node(root->right, q)) ||
//            (Find_node(root->left, q) && Find_node(root->right, p)))
//            return root;
//        else if (Find_node(root->left, p))
//            return lowestCommonAncestor(root->left, p, q);
//        else
//            return lowestCommonAncestor(root->right, p, q);
//    }
//};

//输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
//void _Convert(TreeNode* pRoot, TreeNode*& pPrev)
//{
//    // 空树：不用转化，直接返回
//    if (nullptr == pRoot)
//        return;
//
//    // 将pRoot的左子树转化为双向链表
//    _Convert(pRoot->left, pPrev);
//
//    // pRoot的left指向其前一个处理的节点，即pPrev
//    // pRoot的right域没有办法在本次递归中处理，因为下一个节点不知道
//    // 在本次中只能处理当前节点的left
//    pRoot->left = pPrev;
//
//    // 前一个节点的right指针域没有处理，right指针域指向后一个节点，即pRoot
//    if (pPrev)
//        pPrev->right = pRoot;
//
//    pPrev = pRoot;
//
//    // 将pRoot的右子树转化为双向链表
//    _Convert(pRoot->right, pPrev);
//}
//
//TreeNode* Convert(TreeNode* pRootOfTree)
//{
//    if (nullptr == pRootOfTree)
//        return nullptr;
//
//    // 找双向链表的第一个节点，即树中最小的节点
//    TreeNode* pHead = pRootOfTree;
//    while (pHead->left)
//        pHead = pHead->left;
//
//    // 使用prev标记刚刚转化过的节点
//    TreeNode* prev = nullptr;
//    _Convert(pRootOfTree, prev);
//    return pHead;
//}


//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历
// inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点
//TreeNode* _buildTree(vector<int>& preorder, int& index, vector<int>& inorder, int begin, int end)
//{
//    // index越界时，说明树中的节点已经创建完毕
//    TreeNode* pRoot = nullptr;
//    if (index >= preorder.size())
//        return pRoot;
//
//    // 还原根节点
//    pRoot = new TreeNode(preorder[index]);
//
//    // 在中序遍历结果中找根节点的位置，根节点左侧是是根的左子树，右侧的节点是根的右子树
//    int mid = begin;
//    while (mid < end)
//    {
//        if (inorder[mid] == preorder[index])
//            break;
//
//        mid++;
//    }
//
//    // 左子树存在，递归创建跟节点左子树
//    if (begin < mid)
//    {
//        pRoot->left = _buildTree(preorder, ++index, inorder, begin, mid);
//    }
//
//    // 如果右子树存在，递归创建根节点的右子树
//    if (mid + 1 < end)
//    {
//        pRoot->right = _buildTree(preorder, ++index, inorder, mid + 1, end);
//    }
//
//    return pRoot;
//}
//
//TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//    int index = 0;
//    return _buildTree(preorder, index, inorder, 0, inorder.size());
//}
//递归版本：
//TreeNode* _build(TreeNode*& _root, int& rooti, int left, int right,
//    vector<int>& preorder, vector<int>& inorder)
//{
//    if (left > right)
//        return nullptr;
//    if (left == right)
//    {
//        return new TreeNode(preorder[rooti++]);
//    }
//
//    _root = new TreeNode(preorder[rooti++]);
//    int edge = 0;
//    while (inorder[edge] != preorder[rooti - 1])
//        edge++;
//    _root->left = _build(_root->left, rooti, left, edge - 1, preorder, inorder);
//    _root->right = _build(_root->right, rooti, edge + 1, right, preorder, inorder);
//    return _root;
//}
//TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//    int rooti = 0;
//    TreeNode* root = nullptr;
//    return _build(root, rooti, 0, inorder.size() - 1, preorder, inorder);
//}
//中序与后序还原：
//TreeNode* _build(TreeNode*& _root, int& rooti, int left, int right,
//    vector<int>& postorder, vector<int>& inorder)
//{
//    if (left > right)
//        return nullptr;
//    if (left == right)
//    {
//        return new TreeNode(postorder[rooti--]);
//    }
//
//    _root = new TreeNode(postorder[rooti--]);
//    int edge = 0;
//    while (inorder[edge] != postorder[rooti + 1])
//        edge++;
//    _root->right = _build(_root->right, rooti, edge + 1, right, postorder, inorder);
//    _root->left = _build(_root->left, rooti, left, edge - 1, postorder, inorder);
//    return _root;
//}
//TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//    int rooti = inorder.size() - 1;
//    TreeNode* root = nullptr;
//    return _build(root, rooti, 0, inorder.size() - 1, postorder, inorder);
//}
// 
//二叉树层序遍历：
//vector<vector<int>> levelOrder(TreeNode* root) {
//    vector<vector<int>> vv;
//    queue<TreeNode*> q;
//    int levelsize;
//    if (root)
//    {
//        q.push(root);
//        levelsize = 1;
//    }
//    while (!q.empty())
//    {
//        vector<int> v;
//        for (int i = 0; i < levelsize; i++)
//        {
//            v.push_back(q.front()->val);
//            if (q.front()->left)
//                q.push(q.front()->left);
//            if (q.front()->right)
//                q.push(q.front()->right);
//            q.pop();
//        }
//        vv.push_back(v);
//        levelsize = q.size();
//    }
//    return vv;
//}
//二叉树非递归前序遍历：
//vector<int> preorderTraversal(TreeNode* root) {
//    stack<TreeNode*> st;
//    vector<int> v;
//    while (root || !st.empty())
//    {
//        while (root)
//        {
//            v.push_back(root->val);
//            st.push(root);
//            root = root->left;
//        }
//        TreeNode* top = st.top();
//        st.pop();
//        root = top->right;
//    }
//    return v;
//}
//二叉树非递归中序遍历：
//vector<int> inorderTraversal(TreeNode* root) {
//    stack<TreeNode*> st;
//    vector<int> v;
//    while (root || !st.empty())
//    {
//        while (root)
//        {
//            st.push(root);
//            root = root->left;
//        }
//        TreeNode* top = st.top();
//        st.pop();
//        v.push_back(top->val);
//        root = top->right;
//    }
//    return v;
//}
//二叉树非递归后序遍历：
//vector<int> postorderTraversal(TreeNode* root) {
//    stack<TreeNode*> st;
//    vector<int> v;
//    TreeNode* prev = nullptr;
//    while (root || !st.empty())
//    {
//        while (root)
//        {
//            st.push(root);
//            root = root->left;
//        }
//        TreeNode* top = st.top();
//        if (top->right == nullptr || top->right == prev)
//        {
//            prev = top;
//            v.push_back(top->val);
//            st.pop();
//        }
//        else
//            root = top->right;
//    }
//    return v;
//}
//二叉树的分层遍历(从下向上)
//vector<vector<int>> levelOrderBottom(TreeNode* root) {
//    vector<vector<int>> ans;
//    if (root == nullptr) {
//        return ans;
//    }
//    deque<TreeNode*> q;
//    q.push_back(root);
//    while (!q.empty()) {
//        int size = q.size();
//        vector<int> path;
//        for (int i = 0; i < size; i++) {
//            TreeNode* node = q.front();
//            q.pop_front();
//            path.push_back(node->val);
//            if (node->left != nullptr) {
//                q.push_back(node->left);
//            }
//            if (node->right != nullptr) {
//                q.push_back(node->right);
//            }
//        }
//        ans.push_back(path);
//    }
//    reverse(ans.begin(), ans.end());
//    return ans;
//}